1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import com.google.common.annotations.GwtCompatible;
18 import com.google.common.annotations.GwtIncompatible;
19 import com.google.common.collect.SortedLists.KeyAbsentBehavior;
20 import com.google.common.collect.SortedLists.KeyPresentBehavior;
21 import com.google.common.testing.NullPointerTester;
22
23 import junit.framework.TestCase;
24
25 import java.util.List;
26
27
28
29
30
31
32 @GwtCompatible(emulated = true)
33 public class SortedListsTest extends TestCase {
34 private static final ImmutableList<Integer> LIST_WITH_DUPS =
35 ImmutableList.of(1, 1, 2, 4, 4, 4, 8);
36
37 private static final ImmutableList<Integer> LIST_WITHOUT_DUPS = ImmutableList.of(1, 2, 4, 8);
38
39 void assertModelAgrees(List<Integer> list, Integer key, int answer,
40 KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) {
41 switch (presentBehavior) {
42 case FIRST_PRESENT:
43 if (list.contains(key)) {
44 assertEquals(list.indexOf(key), answer);
45 return;
46 }
47 break;
48 case LAST_PRESENT:
49 if (list.contains(key)) {
50 assertEquals(list.lastIndexOf(key), answer);
51 return;
52 }
53 break;
54 case ANY_PRESENT:
55 if (list.contains(key)) {
56 assertEquals(key, list.get(answer));
57 return;
58 }
59 break;
60 case FIRST_AFTER:
61 if (list.contains(key)) {
62 assertEquals(list.lastIndexOf(key) + 1, answer);
63 return;
64 }
65 break;
66 case LAST_BEFORE:
67 if (list.contains(key)) {
68 assertEquals(list.indexOf(key) - 1, answer);
69 return;
70 }
71 break;
72 default:
73 throw new AssertionError();
74 }
75
76 int nextHigherIndex = list.size();
77 for (int i = list.size() - 1; i >= 0 && list.get(i) > key; i--) {
78 nextHigherIndex = i;
79 }
80 switch (absentBehavior) {
81 case NEXT_LOWER:
82 assertEquals(nextHigherIndex - 1, answer);
83 return;
84 case NEXT_HIGHER:
85 assertEquals(nextHigherIndex, answer);
86 return;
87 case INVERTED_INSERTION_INDEX:
88 assertEquals(-1 - nextHigherIndex, answer);
89 return;
90 default:
91 throw new AssertionError();
92 }
93 }
94
95 public void testWithoutDups() {
96 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) {
97 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) {
98 for (int key = 0; key <= 10; key++) {
99 assertModelAgrees(LIST_WITHOUT_DUPS, key,
100 SortedLists.binarySearch(LIST_WITHOUT_DUPS, key, presentBehavior, absentBehavior),
101 presentBehavior, absentBehavior);
102 }
103 }
104 }
105 }
106
107 public void testWithDups() {
108 for (KeyPresentBehavior presentBehavior : KeyPresentBehavior.values()) {
109 for (KeyAbsentBehavior absentBehavior : KeyAbsentBehavior.values()) {
110 for (int key = 0; key <= 10; key++) {
111 assertModelAgrees(LIST_WITH_DUPS, key,
112 SortedLists.binarySearch(LIST_WITH_DUPS, key, presentBehavior, absentBehavior),
113 presentBehavior, absentBehavior);
114 }
115 }
116 }
117 }
118
119 @GwtIncompatible("NullPointerTester")
120 public void testNulls() {
121 new NullPointerTester().testAllPublicStaticMethods(SortedLists.class);
122 }
123 }